//
//public class antAlgorithm{
//    public Ant[] ants; // 蚂蚁
//    public int antNum = 2; // 蚂蚁数量
//    public int squareNum; // 矩形数量
//    public int MAX_GEN = 20; // 最大迭代数
//    public double[][] pheromone; // 信息素矩阵
//    public double[][] different; // 不同度矩阵
//    public double bestRate; // 最佳利用率
//    public int[] bestSquence; // 最佳放置顺序
//    public int bestT; //最佳迭代数
//    public List<Square> squareList; // 矩形集合
//    // 问题实例
//    public Instance instance;
//    // 大矩形（容器）的长宽
//    double L, W;
//    public Solution bestSolution; //最优解
//
//    // 三个参数
//    private double alpha = 1; //信息素重要程度
//    private double beta = 5; //启发式因子重要程度
//    private double rho = 0.5; //信息素挥发速率
//
//    // 构造函数
//    public ACO_Packing(Instance instance) {
//        this.squareList = instance.getSquareList();
//        this.instance = instance;
//        this.L = instance.getL();
//        this.W = instance.getW();
//        squareNum = squareList.size();
//        ants = new Ant[antNum];
//    }
//
//    // 外部调用窗口
//    public Solution search() {
//        long startTime = System.currentTimeMillis();
//        initVar();
//        bestSolution = solve();
//        long endTime = System.currentTimeMillis();
//        //求解完毕
//        System.out.println("最佳迭代次数:"+bestT);
//        System.out.println("最佳利用率为:"+bestSolution.getRate());
//        System.out.println("程序运行了：" + (endTime - startTime) / 1000.0 + "秒");
//        return bestSolution;
//    }
//
//    // 蚁群算法迭代求解
//    public Solution solve() {
//        // 迭代MAX_GEN次
//        for (int g = 0; g < MAX_GEN; g++) {
//            // antNum只蚂蚁
//            for (int i = 0; i < antNum; i++) {
//                // i这只蚂蚁走squareNum步，构成一个完整的矩形放置顺序
//                for (int j = 1; j < squareNum; j++) {
//                    ants[i].selectNextSquare(pheromone);
//                }
//                // 把这只蚂蚁初始放置矩形加入其禁忌表中
//                ants[i].getTabu().add(ants[i].getFirstSquare());
//                // 查看这只蚂蚁装载利用率是否比当前最优解优秀
//                ants[i].calculateTotalPlaceSquareS();
//                if (ants[i].getLocalSolution().getRate() > bestRate) {
//                    // 比当前优秀则拷贝优秀的放置顺序
//                    bestRate = ants[i].getLocalSolution().getRate();
//                    for (int k = 0; k < squareNum; k++) {
//                        bestSquence[k] = ants[i].getTabu().get(k);
//                    }
//                    bestT = g;
//                    bestSolution = ants[i].getLocalSolution();
//                    System.out.println("蚂蚁"+(i+1)+": 当前迭代次数为："+g+",当前最佳利用率为："+bestSolution.getRate());
//                }
//                // 更新这只蚂蚁的信息数变化矩阵，对称矩阵
//                for (int j = 0; j < squareNum; j++) {
//                    ants[i].getDelta()[ants[i].getTabu().get(j)][ants[i]
//                            .getTabu().get(j + 1)] = (1.0 / ants[i]
//                            .getLocalSolution().getRate());
//                    ants[i].getDelta()[ants[i].getTabu().get(j + 1)][ants[i]
//                            .getTabu().get(j)] = (1.0 / ants[i]
//                            .getLocalSolution().getRate());
//                }
//            }
//            // 更新信息素
//            updatePheromone();
//            // 重新初始化蚂蚁
//            for (int i = 0; i < antNum; i++) {
//                ants[i].initAnt(different, alpha, beta);
//            }
//        }
//        // 返回结果
//        return bestSolution;
//    }
//
//    //初始化
//    public void initVar() {
//        bestSolution = new Solution();
//        //初始化不同度矩阵
//        different = new double[squareNum][squareNum];
//        for (int i = 0; i < squareNum; i++) {
//            for (int j = 0; j < squareNum; j++) {
//                if (i == j) {
//                    different[i][j] = 0.0;
//                } else {
//                    different[i][j] = getDifferent(squareList.get(i), squareList.get(j));
//                }
//            }
//        }
//        //初始化信息素矩阵
//        pheromone = new double[squareNum][squareNum];
//        for (int i = 0; i < squareNum; i++) {
//            for (int j = 0; j < squareNum; j++) {
//                pheromone[i][j] = 0.1; // 初始化为0.1
//            }
//        }
//        bestRate = 0d;
//        bestSquence = new int[squareNum];
//        // 放置蚂蚁
//        for (int i = 0; i < antNum; i++) {
//            ants[i] = new Ant(squareNum,squareList,L,W,instance);
//            ants[i].initAnt(different, alpha, beta);
//        }
//    }
//
//    // 更新信息素
//    private void updatePheromone() {
//        // 信息素挥发
//        for (int i = 0; i < squareNum; i++) {
//                for (int j = 0; j < squareNum; j++) {
//                    pheromone[i][j] = pheromone[i][j] * (1 - rho);
//                }
//        }
//        // 信息素更新
//        for (int i = 0; i < squareNum; i++) {
//            for (int j = 0; j < squareNum; j++) {
//                for (int k = 0; k < antNum; k++) {
//                    pheromone[i][j] += ants[k].getDelta()[i][j];
//                }
//            }
//        }
//    }
//
//    //计算矩形A对B的不同度
//    public double getDifferent(Square A, Square B) {
//        double different = 0d;
//        different += Math.abs(A.getL()-B.getL())/B.getL();
//        different += Math.abs(A.getW()-B.getW())/B.getW();
//        return different;
//    }
//
//}
